package com.yvon.service.demo.algorithm.offer;

import com.yvon.service.demo.algorithm.offer.ext.Node;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 二叉搜索树与双向链表
 * 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。
 * https://doocs.gitee.io/leetcode/#/lcof/%E9%9D%A2%E8%AF%95%E9%A2%9836.%20%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E4%B8%8E%E5%8F%8C%E5%90%91%E9%93%BE%E8%A1%A8/README
 */
public class P36 {

    public static void main(String[] args) {

    }

    class Solution {
        public Node treeToDoublyList(Node root) {
            Deque<Node> queue = new ArrayDeque<>();
            inOrder(root, queue);
            Node head = queue.poll();
            Node pre = head;
            while (!queue.isEmpty()) {
                Node cur = queue.poll();
                pre.right = cur;
                cur.left = pre;
                pre = cur;
            }
            pre.right = head;
            head.left = pre;
            return head;
        }

        /**
         * 中序遍历
         */
        void inOrder(Node root, Deque<Node> queue) {
            if (root == null) {
                return;
            }
            inOrder(root.left, queue);
            queue.add(root);
            inOrder(root.right, queue);
        }
    }
}
